/*
 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
 * Released under the terms of the GNU GPL v2.0.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lkc.h"

#define DEBUG_EXPR	0

static int expr_eq(struct expr* e1, struct expr* e2);
static struct expr* expr_eliminate_yn(struct expr* e);

struct expr* expr_alloc_symbol(struct symbol* sym)
{
	struct expr* e = xcalloc(1, sizeof(*e));
	e->type = E_SYMBOL;
	e->left.sym = sym;
	return e;
}

struct expr* expr_alloc_one(enum expr_type type, struct expr* ce)
{
	struct expr* e = xcalloc(1, sizeof(*e));
	e->type = type;
	e->left.expr = ce;
	return e;
}

struct expr* expr_alloc_two(enum expr_type type, struct expr* e1, struct expr* e2)
{
	struct expr* e = xcalloc(1, sizeof(*e));
	e->type = type;
	e->left.expr = e1;
	e->right.expr = e2;
	return e;
}

struct expr* expr_alloc_comp(enum expr_type type, struct symbol* s1, struct symbol* s2)
{
	struct expr* e = xcalloc(1, sizeof(*e));
	e->type = type;
	e->left.sym = s1;
	e->right.sym = s2;
	return e;
}

struct expr* expr_alloc_and(struct expr* e1, struct expr* e2)
{
	if(!e1)
		return e2;

	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
}

struct expr* expr_alloc_or(struct expr* e1, struct expr* e2)
{
	if(!e1)
		return e2;

	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
}

struct expr* expr_copy(const struct expr* org)
{
	struct expr* e;

	if(!org)
		return NULL;

	e = xmalloc(sizeof(*org));
	memcpy(e, org, sizeof(*org));

	switch(org->type) {
		case E_SYMBOL:
			e->left = org->left;
			break;

		case E_NOT:
			e->left.expr = expr_copy(org->left.expr);
			break;

		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
			e->left.sym = org->left.sym;
			e->right.sym = org->right.sym;
			break;

		case E_AND:
		case E_OR:
		case E_LIST:
			e->left.expr = expr_copy(org->left.expr);
			e->right.expr = expr_copy(org->right.expr);
			break;

		default:
			printf("can't copy type %d\n", e->type);
			free(e);
			e = NULL;
			break;
	}

	return e;
}

void expr_free(struct expr* e)
{
	if(!e)
		return;

	switch(e->type) {
		case E_SYMBOL:
			break;

		case E_NOT:
			expr_free(e->left.expr);
			return;

		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
			break;

		case E_OR:
		case E_AND:
			expr_free(e->left.expr);
			expr_free(e->right.expr);
			break;

		default:
			printf("how to free type %d?\n", e->type);
			break;
	}

	free(e);
}

static int trans_count;

#define e1 (*ep1)
#define e2 (*ep2)

static void __expr_eliminate_eq(enum expr_type type, struct expr** ep1, struct expr** ep2)
{
	if(e1->type == type) {
		__expr_eliminate_eq(type, &e1->left.expr, &e2);
		__expr_eliminate_eq(type, &e1->right.expr, &e2);
		return;
	}

	if(e2->type == type) {
		__expr_eliminate_eq(type, &e1, &e2->left.expr);
		__expr_eliminate_eq(type, &e1, &e2->right.expr);
		return;
	}

	if(e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
	        e1->left.sym == e2->left.sym &&
	        (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
		return;

	if(!expr_eq(e1, e2))
		return;

	trans_count++;
	expr_free(e1);
	expr_free(e2);

	switch(type) {
		case E_OR:
			e1 = expr_alloc_symbol(&symbol_no);
			e2 = expr_alloc_symbol(&symbol_no);
			break;

		case E_AND:
			e1 = expr_alloc_symbol(&symbol_yes);
			e2 = expr_alloc_symbol(&symbol_yes);
			break;

		default:
			;
	}
}

void expr_eliminate_eq(struct expr** ep1, struct expr** ep2)
{
	if(!e1 || !e2)
		return;

	switch(e1->type) {
		case E_OR:
		case E_AND:
			__expr_eliminate_eq(e1->type, ep1, ep2);

		default:
			;
	}

	if(e1->type != e2->type) switch(e2->type) {
			case E_OR:
			case E_AND:
				__expr_eliminate_eq(e2->type, ep1, ep2);

			default:
				;
		}

	e1 = expr_eliminate_yn(e1);
	e2 = expr_eliminate_yn(e2);
}

#undef e1
#undef e2

static int expr_eq(struct expr* e1, struct expr* e2)
{
	int res, old_count;

	if(e1->type != e2->type)
		return 0;

	switch(e1->type) {
		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
			return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;

		case E_SYMBOL:
			return e1->left.sym == e2->left.sym;

		case E_NOT:
			return expr_eq(e1->left.expr, e2->left.expr);

		case E_AND:
		case E_OR:
			e1 = expr_copy(e1);
			e2 = expr_copy(e2);
			old_count = trans_count;
			expr_eliminate_eq(&e1, &e2);
			res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
			       e1->left.sym == e2->left.sym);
			expr_free(e1);
			expr_free(e2);
			trans_count = old_count;
			return res;

		case E_LIST:
		case E_RANGE:
		case E_NONE:
			/* panic */
			;
	}

	if(DEBUG_EXPR) {
		expr_fprint(e1, stdout);
		printf(" = ");
		expr_fprint(e2, stdout);
		printf(" ?\n");
	}

	return 0;
}

static struct expr* expr_eliminate_yn(struct expr* e)
{
	struct expr* tmp;

	if(e) switch(e->type) {
			case E_AND:
				e->left.expr = expr_eliminate_yn(e->left.expr);
				e->right.expr = expr_eliminate_yn(e->right.expr);

				if(e->left.expr->type == E_SYMBOL) {
					if(e->left.expr->left.sym == &symbol_no) {
						expr_free(e->left.expr);
						expr_free(e->right.expr);
						e->type = E_SYMBOL;
						e->left.sym = &symbol_no;
						e->right.expr = NULL;
						return e;
					} else if(e->left.expr->left.sym == &symbol_yes) {
						free(e->left.expr);
						tmp = e->right.expr;
						*e = *(e->right.expr);
						free(tmp);
						return e;
					}
				}

				if(e->right.expr->type == E_SYMBOL) {
					if(e->right.expr->left.sym == &symbol_no) {
						expr_free(e->left.expr);
						expr_free(e->right.expr);
						e->type = E_SYMBOL;
						e->left.sym = &symbol_no;
						e->right.expr = NULL;
						return e;
					} else if(e->right.expr->left.sym == &symbol_yes) {
						free(e->right.expr);
						tmp = e->left.expr;
						*e = *(e->left.expr);
						free(tmp);
						return e;
					}
				}

				break;

			case E_OR:
				e->left.expr = expr_eliminate_yn(e->left.expr);
				e->right.expr = expr_eliminate_yn(e->right.expr);

				if(e->left.expr->type == E_SYMBOL) {
					if(e->left.expr->left.sym == &symbol_no) {
						free(e->left.expr);
						tmp = e->right.expr;
						*e = *(e->right.expr);
						free(tmp);
						return e;
					} else if(e->left.expr->left.sym == &symbol_yes) {
						expr_free(e->left.expr);
						expr_free(e->right.expr);
						e->type = E_SYMBOL;
						e->left.sym = &symbol_yes;
						e->right.expr = NULL;
						return e;
					}
				}

				if(e->right.expr->type == E_SYMBOL) {
					if(e->right.expr->left.sym == &symbol_no) {
						free(e->right.expr);
						tmp = e->left.expr;
						*e = *(e->left.expr);
						free(tmp);
						return e;
					} else if(e->right.expr->left.sym == &symbol_yes) {
						expr_free(e->left.expr);
						expr_free(e->right.expr);
						e->type = E_SYMBOL;
						e->left.sym = &symbol_yes;
						e->right.expr = NULL;
						return e;
					}
				}

				break;

			default:
				;
		}

	return e;
}

/*
 * bool FOO!=n => FOO
 */
struct expr* expr_trans_bool(struct expr* e)
{
	if(!e)
		return NULL;

	switch(e->type) {
		case E_AND:
		case E_OR:
		case E_NOT:
			e->left.expr = expr_trans_bool(e->left.expr);
			e->right.expr = expr_trans_bool(e->right.expr);
			break;

		case E_UNEQUAL:

			// FOO!=n -> FOO
			if(e->left.sym->type == S_TRISTATE) {
				if(e->right.sym == &symbol_no) {
					e->type = E_SYMBOL;
					e->right.sym = NULL;
				}
			}

			break;

		default:
			;
	}

	return e;
}

/*
 * e1 || e2 -> ?
 */
static struct expr* expr_join_or(struct expr* e1, struct expr* e2)
{
	struct expr* tmp;
	struct symbol* sym1, *sym2;

	if(expr_eq(e1, e2))
		return expr_copy(e1);

	if(e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
		return NULL;

	if(e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
		return NULL;

	if(e1->type == E_NOT) {
		tmp = e1->left.expr;

		if(tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
			return NULL;

		sym1 = tmp->left.sym;
	} else
		sym1 = e1->left.sym;

	if(e2->type == E_NOT) {
		if(e2->left.expr->type != E_SYMBOL)
			return NULL;

		sym2 = e2->left.expr->left.sym;
	} else
		sym2 = e2->left.sym;

	if(sym1 != sym2)
		return NULL;

	if(sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
		return NULL;

	if(sym1->type == S_TRISTATE) {
		if(e1->type == E_EQUAL && e2->type == E_EQUAL &&
		        ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
		         (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
			// (a='y') || (a='m') -> (a!='n')
			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
		}

		if(e1->type == E_EQUAL && e2->type == E_EQUAL &&
		        ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
		         (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
			// (a='y') || (a='n') -> (a!='m')
			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
		}

		if(e1->type == E_EQUAL && e2->type == E_EQUAL &&
		        ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
		         (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
			// (a='m') || (a='n') -> (a!='y')
			return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
		}
	}

	if(sym1->type == S_BOOLEAN && sym1 == sym2) {
		if((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
		        (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
			return expr_alloc_symbol(&symbol_yes);
	}

	if(DEBUG_EXPR) {
		printf("optimize (");
		expr_fprint(e1, stdout);
		printf(") || (");
		expr_fprint(e2, stdout);
		printf(")?\n");
	}

	return NULL;
}

static struct expr* expr_join_and(struct expr* e1, struct expr* e2)
{
	struct expr* tmp;
	struct symbol* sym1, *sym2;

	if(expr_eq(e1, e2))
		return expr_copy(e1);

	if(e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
		return NULL;

	if(e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
		return NULL;

	if(e1->type == E_NOT) {
		tmp = e1->left.expr;

		if(tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
			return NULL;

		sym1 = tmp->left.sym;
	} else
		sym1 = e1->left.sym;

	if(e2->type == E_NOT) {
		if(e2->left.expr->type != E_SYMBOL)
			return NULL;

		sym2 = e2->left.expr->left.sym;
	} else
		sym2 = e2->left.sym;

	if(sym1 != sym2)
		return NULL;

	if(sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
		return NULL;

	if((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
	        (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
		// (a) && (a='y') -> (a='y')
		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

	if((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
	        (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
		// (a) && (a!='n') -> (a)
		return expr_alloc_symbol(sym1);

	if((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
	        (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
		// (a) && (a!='m') -> (a='y')
		return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

	if(sym1->type == S_TRISTATE) {
		if(e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
			sym2 = e1->right.sym;

			if((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
				return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
				       : expr_alloc_symbol(&symbol_no);
		}

		if(e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
			// (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
			sym2 = e2->right.sym;

			if((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
				return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
				       : expr_alloc_symbol(&symbol_no);
		}

		if(e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
		        ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
		         (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
			// (a!='y') && (a!='n') -> (a='m')
			return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);

		if(e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
		        ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
		         (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
			// (a!='y') && (a!='m') -> (a='n')
			return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);

		if(e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
		        ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
		         (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
			// (a!='m') && (a!='n') -> (a='m')
			return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);

		if((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
		        (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
		        (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
		        (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
			return NULL;
	}

	if(DEBUG_EXPR) {
		printf("optimize (");
		expr_fprint(e1, stdout);
		printf(") && (");
		expr_fprint(e2, stdout);
		printf(")?\n");
	}

	return NULL;
}

static void expr_eliminate_dups1(enum expr_type type, struct expr** ep1, struct expr** ep2)
{
#define e1 (*ep1)
#define e2 (*ep2)
	struct expr* tmp;

	if(e1->type == type) {
		expr_eliminate_dups1(type, &e1->left.expr, &e2);
		expr_eliminate_dups1(type, &e1->right.expr, &e2);
		return;
	}

	if(e2->type == type) {
		expr_eliminate_dups1(type, &e1, &e2->left.expr);
		expr_eliminate_dups1(type, &e1, &e2->right.expr);
		return;
	}

	if(e1 == e2)
		return;

	switch(e1->type) {
		case E_OR:
		case E_AND:
			expr_eliminate_dups1(e1->type, &e1, &e1);

		default:
			;
	}

	switch(type) {
		case E_OR:
			tmp = expr_join_or(e1, e2);

			if(tmp) {
				expr_free(e1);
				expr_free(e2);
				e1 = expr_alloc_symbol(&symbol_no);
				e2 = tmp;
				trans_count++;
			}

			break;

		case E_AND:
			tmp = expr_join_and(e1, e2);

			if(tmp) {
				expr_free(e1);
				expr_free(e2);
				e1 = expr_alloc_symbol(&symbol_yes);
				e2 = tmp;
				trans_count++;
			}

			break;

		default:
			;
	}

#undef e1
#undef e2
}

struct expr* expr_eliminate_dups(struct expr* e)
{
	int oldcount;

	if(!e)
		return e;

	oldcount = trans_count;

	while(1) {
		trans_count = 0;

		switch(e->type) {
			case E_OR:
			case E_AND:
				expr_eliminate_dups1(e->type, &e, &e);

			default:
				;
		}

		if(!trans_count)
			break;

		e = expr_eliminate_yn(e);
	}

	trans_count = oldcount;
	return e;
}

struct expr* expr_transform(struct expr* e)
{
	struct expr* tmp;

	if(!e)
		return NULL;

	switch(e->type) {
		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
		case E_SYMBOL:
		case E_LIST:
			break;

		default:
			e->left.expr = expr_transform(e->left.expr);
			e->right.expr = expr_transform(e->right.expr);
	}

	switch(e->type) {
		case E_EQUAL:
			if(e->left.sym->type != S_BOOLEAN)
				break;

			if(e->right.sym == &symbol_no) {
				e->type = E_NOT;
				e->left.expr = expr_alloc_symbol(e->left.sym);
				e->right.sym = NULL;
				break;
			}

			if(e->right.sym == &symbol_mod) {
				printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
				e->type = E_SYMBOL;
				e->left.sym = &symbol_no;
				e->right.sym = NULL;
				break;
			}

			if(e->right.sym == &symbol_yes) {
				e->type = E_SYMBOL;
				e->right.sym = NULL;
				break;
			}

			break;

		case E_UNEQUAL:
			if(e->left.sym->type != S_BOOLEAN)
				break;

			if(e->right.sym == &symbol_no) {
				e->type = E_SYMBOL;
				e->right.sym = NULL;
				break;
			}

			if(e->right.sym == &symbol_mod) {
				printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
				e->type = E_SYMBOL;
				e->left.sym = &symbol_yes;
				e->right.sym = NULL;
				break;
			}

			if(e->right.sym == &symbol_yes) {
				e->type = E_NOT;
				e->left.expr = expr_alloc_symbol(e->left.sym);
				e->right.sym = NULL;
				break;
			}

			break;

		case E_NOT:
			switch(e->left.expr->type) {
				case E_NOT:
					// !!a -> a
					tmp = e->left.expr->left.expr;
					free(e->left.expr);
					free(e);
					e = tmp;
					e = expr_transform(e);
					break;

				case E_EQUAL:
				case E_UNEQUAL:
					// !a='x' -> a!='x'
					tmp = e->left.expr;
					free(e);
					e = tmp;
					e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
					break;

				case E_LEQ:
				case E_GEQ:
					// !a<='x' -> a>'x'
					tmp = e->left.expr;
					free(e);
					e = tmp;
					e->type = e->type == E_LEQ ? E_GTH : E_LTH;
					break;

				case E_LTH:
				case E_GTH:
					// !a<'x' -> a>='x'
					tmp = e->left.expr;
					free(e);
					e = tmp;
					e->type = e->type == E_LTH ? E_GEQ : E_LEQ;
					break;

				case E_OR:
					// !(a || b) -> !a && !b
					tmp = e->left.expr;
					e->type = E_AND;
					e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
					tmp->type = E_NOT;
					tmp->right.expr = NULL;
					e = expr_transform(e);
					break;

				case E_AND:
					// !(a && b) -> !a || !b
					tmp = e->left.expr;
					e->type = E_OR;
					e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
					tmp->type = E_NOT;
					tmp->right.expr = NULL;
					e = expr_transform(e);
					break;

				case E_SYMBOL:
					if(e->left.expr->left.sym == &symbol_yes) {
						// !'y' -> 'n'
						tmp = e->left.expr;
						free(e);
						e = tmp;
						e->type = E_SYMBOL;
						e->left.sym = &symbol_no;
						break;
					}

					if(e->left.expr->left.sym == &symbol_mod) {
						// !'m' -> 'm'
						tmp = e->left.expr;
						free(e);
						e = tmp;
						e->type = E_SYMBOL;
						e->left.sym = &symbol_mod;
						break;
					}

					if(e->left.expr->left.sym == &symbol_no) {
						// !'n' -> 'y'
						tmp = e->left.expr;
						free(e);
						e = tmp;
						e->type = E_SYMBOL;
						e->left.sym = &symbol_yes;
						break;
					}

					break;

				default:
					;
			}

			break;

		default:
			;
	}

	return e;
}

int expr_contains_symbol(struct expr* dep, struct symbol* sym)
{
	if(!dep)
		return 0;

	switch(dep->type) {
		case E_AND:
		case E_OR:
			return expr_contains_symbol(dep->left.expr, sym) ||
			       expr_contains_symbol(dep->right.expr, sym);

		case E_SYMBOL:
			return dep->left.sym == sym;

		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
			return dep->left.sym == sym ||
			       dep->right.sym == sym;

		case E_NOT:
			return expr_contains_symbol(dep->left.expr, sym);

		default:
			;
	}

	return 0;
}

bool expr_depends_symbol(struct expr* dep, struct symbol* sym)
{
	if(!dep)
		return false;

	switch(dep->type) {
		case E_AND:
			return expr_depends_symbol(dep->left.expr, sym) ||
			       expr_depends_symbol(dep->right.expr, sym);

		case E_SYMBOL:
			return dep->left.sym == sym;

		case E_EQUAL:
			if(dep->left.sym == sym) {
				if(dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
					return true;
			}

			break;

		case E_UNEQUAL:
			if(dep->left.sym == sym) {
				if(dep->right.sym == &symbol_no)
					return true;
			}

			break;

		default:
			;
	}

	return false;
}

struct expr* expr_trans_compare(struct expr* e, enum expr_type type, struct symbol* sym)
{
	struct expr* e1, *e2;

	if(!e) {
		e = expr_alloc_symbol(sym);

		if(type == E_UNEQUAL)
			e = expr_alloc_one(E_NOT, e);

		return e;
	}

	switch(e->type) {
		case E_AND:
			e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
			e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);

			if(sym == &symbol_yes)
				e = expr_alloc_two(E_AND, e1, e2);

			if(sym == &symbol_no)
				e = expr_alloc_two(E_OR, e1, e2);

			if(type == E_UNEQUAL)
				e = expr_alloc_one(E_NOT, e);

			return e;

		case E_OR:
			e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
			e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);

			if(sym == &symbol_yes)
				e = expr_alloc_two(E_OR, e1, e2);

			if(sym == &symbol_no)
				e = expr_alloc_two(E_AND, e1, e2);

			if(type == E_UNEQUAL)
				e = expr_alloc_one(E_NOT, e);

			return e;

		case E_NOT:
			return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);

		case E_UNEQUAL:
		case E_LTH:
		case E_LEQ:
		case E_GTH:
		case E_GEQ:
		case E_EQUAL:
			if(type == E_EQUAL) {
				if(sym == &symbol_yes)
					return expr_copy(e);

				if(sym == &symbol_mod)
					return expr_alloc_symbol(&symbol_no);

				if(sym == &symbol_no)
					return expr_alloc_one(E_NOT, expr_copy(e));
			} else {
				if(sym == &symbol_yes)
					return expr_alloc_one(E_NOT, expr_copy(e));

				if(sym == &symbol_mod)
					return expr_alloc_symbol(&symbol_yes);

				if(sym == &symbol_no)
					return expr_copy(e);
			}

			break;

		case E_SYMBOL:
			return expr_alloc_comp(type, e->left.sym, sym);

		case E_LIST:
		case E_RANGE:
		case E_NONE:
			/* panic */
			;
	}

	return NULL;
}

enum string_value_kind {
	k_string,
	k_signed,
	k_unsigned,
	k_invalid
};

union string_value {
	unsigned long long u;
	signed long long s;
};

static enum string_value_kind expr_parse_string(const char* str,
        enum symbol_type type,
        union string_value* val)
{
	char* tail;
	enum string_value_kind kind;

	errno = 0;

	switch(type) {
		case S_BOOLEAN:
		case S_TRISTATE:
			return k_string;

		case S_INT:
			val->s = strtoll(str, &tail, 10);
			kind = k_signed;
			break;

		case S_HEX:
			val->u = strtoull(str, &tail, 16);
			kind = k_unsigned;
			break;

		case S_STRING:
		case S_UNKNOWN:
			val->s = strtoll(str, &tail, 0);
			kind = k_signed;
			break;

		default:
			return k_invalid;
	}

	return !errno && !*tail && tail > str && isxdigit(tail[-1])
	       ? kind : k_string;
}

tristate expr_calc_value(struct expr* e)
{
	tristate val1, val2;
	const char* str1, *str2;
	enum string_value_kind k1 = k_string, k2 = k_string;
	union string_value lval = {}, rval = {};
	int res;

	if(!e)
		return yes;

	switch(e->type) {
		case E_SYMBOL:
			sym_calc_value(e->left.sym);
			return e->left.sym->curr.tri;

		case E_AND:
			val1 = expr_calc_value(e->left.expr);
			val2 = expr_calc_value(e->right.expr);
			return EXPR_AND(val1, val2);

		case E_OR:
			val1 = expr_calc_value(e->left.expr);
			val2 = expr_calc_value(e->right.expr);
			return EXPR_OR(val1, val2);

		case E_NOT:
			val1 = expr_calc_value(e->left.expr);
			return EXPR_NOT(val1);

		case E_EQUAL:
		case E_GEQ:
		case E_GTH:
		case E_LEQ:
		case E_LTH:
		case E_UNEQUAL:
			break;

		default:
			printf("expr_calc_value: %d?\n", e->type);
			return no;
	}

	sym_calc_value(e->left.sym);
	sym_calc_value(e->right.sym);
	str1 = sym_get_string_value(e->left.sym);
	str2 = sym_get_string_value(e->right.sym);

	if(e->left.sym->type != S_STRING || e->right.sym->type != S_STRING) {
		k1 = expr_parse_string(str1, e->left.sym->type, &lval);
		k2 = expr_parse_string(str2, e->right.sym->type, &rval);
	}

	if(k1 == k_string || k2 == k_string)
		res = strcmp(str1, str2);
	else if(k1 == k_invalid || k2 == k_invalid) {
		if(e->type != E_EQUAL && e->type != E_UNEQUAL) {
			printf("Cannot compare \"%s\" and \"%s\"\n", str1, str2);
			return no;
		}

		res = strcmp(str1, str2);
	} else if(k1 == k_unsigned || k2 == k_unsigned)
		res = (lval.u > rval.u) - (lval.u < rval.u);
	else /* if (k1 == k_signed && k2 == k_signed) */
		res = (lval.s > rval.s) - (lval.s < rval.s);

	switch(e->type) {
		case E_EQUAL:
			return res ? no : yes;

		case E_GEQ:
			return res >= 0 ? yes : no;

		case E_GTH:
			return res > 0 ? yes : no;

		case E_LEQ:
			return res <= 0 ? yes : no;

		case E_LTH:
			return res < 0 ? yes : no;

		case E_UNEQUAL:
			return res ? yes : no;

		default:
			printf("expr_calc_value: relation %d?\n", e->type);
			return no;
	}
}

static int expr_compare_type(enum expr_type t1, enum expr_type t2)
{
	if(t1 == t2)
		return 0;

	switch(t1) {
		case E_LEQ:
		case E_LTH:
		case E_GEQ:
		case E_GTH:
			if(t2 == E_EQUAL || t2 == E_UNEQUAL)
				return 1;

		case E_EQUAL:
		case E_UNEQUAL:
			if(t2 == E_NOT)
				return 1;

		case E_NOT:
			if(t2 == E_AND)
				return 1;

		case E_AND:
			if(t2 == E_OR)
				return 1;

		case E_OR:
			if(t2 == E_LIST)
				return 1;

		case E_LIST:
			if(t2 == 0)
				return 1;

		default:
			return -1;
	}

	printf("[%dgt%d?]", t1, t2);
	return 0;
}

static inline struct expr*
expr_get_leftmost_symbol(const struct expr* e)
{

	if(e == NULL)
		return NULL;

	while(e->type != E_SYMBOL)
		e = e->left.expr;

	return expr_copy(e);
}

/*
 * Given expression `e1' and `e2', returns the leaf of the longest
 * sub-expression of `e1' not containing 'e2.
 */
struct expr* expr_simplify_unmet_dep(struct expr* e1, struct expr* e2)
{
	struct expr* ret;

	switch(e1->type) {
		case E_OR:
			return expr_alloc_and(
			           expr_simplify_unmet_dep(e1->left.expr, e2),
			           expr_simplify_unmet_dep(e1->right.expr, e2));

		case E_AND: {
			struct expr* e;
			e = expr_alloc_and(expr_copy(e1), expr_copy(e2));
			e = expr_eliminate_dups(e);
			ret = (!expr_eq(e, e1)) ? e1 : NULL;
			expr_free(e);
			break;
		}

		default:
			ret = e1;
			break;
	}

	return expr_get_leftmost_symbol(ret);
}

void expr_print(struct expr* e, void (*fn)(void*, struct symbol*, const char*), void* data, int prevtoken)
{
	if(!e) {
		fn(data, NULL, "y");
		return;
	}

	if(expr_compare_type(prevtoken, e->type) > 0)
		fn(data, NULL, "(");

	switch(e->type) {
		case E_SYMBOL:
			if(e->left.sym->name)
				fn(data, e->left.sym, e->left.sym->name);
			else
				fn(data, NULL, "<choice>");

			break;

		case E_NOT:
			fn(data, NULL, "!");
			expr_print(e->left.expr, fn, data, E_NOT);
			break;

		case E_EQUAL:
			if(e->left.sym->name)
				fn(data, e->left.sym, e->left.sym->name);
			else
				fn(data, NULL, "<choice>");

			fn(data, NULL, "=");
			fn(data, e->right.sym, e->right.sym->name);
			break;

		case E_LEQ:
		case E_LTH:
			if(e->left.sym->name)
				fn(data, e->left.sym, e->left.sym->name);
			else
				fn(data, NULL, "<choice>");

			fn(data, NULL, e->type == E_LEQ ? "<=" : "<");
			fn(data, e->right.sym, e->right.sym->name);
			break;

		case E_GEQ:
		case E_GTH:
			if(e->left.sym->name)
				fn(data, e->left.sym, e->left.sym->name);
			else
				fn(data, NULL, "<choice>");

			fn(data, NULL, e->type == E_GEQ ? ">=" : ">");
			fn(data, e->right.sym, e->right.sym->name);
			break;

		case E_UNEQUAL:
			if(e->left.sym->name)
				fn(data, e->left.sym, e->left.sym->name);
			else
				fn(data, NULL, "<choice>");

			fn(data, NULL, "!=");
			fn(data, e->right.sym, e->right.sym->name);
			break;

		case E_OR:
			expr_print(e->left.expr, fn, data, E_OR);
			fn(data, NULL, " || ");
			expr_print(e->right.expr, fn, data, E_OR);
			break;

		case E_AND:
			expr_print(e->left.expr, fn, data, E_AND);
			fn(data, NULL, " && ");
			expr_print(e->right.expr, fn, data, E_AND);
			break;

		case E_LIST:
			fn(data, e->right.sym, e->right.sym->name);

			if(e->left.expr) {
				fn(data, NULL, " ^ ");
				expr_print(e->left.expr, fn, data, E_LIST);
			}

			break;

		case E_RANGE:
			fn(data, NULL, "[");
			fn(data, e->left.sym, e->left.sym->name);
			fn(data, NULL, " ");
			fn(data, e->right.sym, e->right.sym->name);
			fn(data, NULL, "]");
			break;

		default: {
			char buf[32];
			sprintf(buf, "<unknown type %d>", e->type);
			fn(data, NULL, buf);
			break;
		}
	}

	if(expr_compare_type(prevtoken, e->type) > 0)
		fn(data, NULL, ")");
}

static void expr_print_file_helper(void* data, struct symbol* sym, const char* str)
{
	xfwrite(str, strlen(str), 1, data);
}

void expr_fprint(struct expr* e, FILE* out)
{
	expr_print(e, expr_print_file_helper, out, E_NONE);
}

static void expr_print_gstr_helper(void* data, struct symbol* sym, const char* str)
{
	struct gstr* gs = (struct gstr*)data;
	const char* sym_str = NULL;

	if(sym)
		sym_str = sym_get_string_value(sym);

	if(gs->max_width) {
		unsigned extra_length = strlen(str);
		const char* last_cr = strrchr(gs->s, '\n');
		unsigned last_line_length;

		if(sym_str)
			extra_length += 4 + strlen(sym_str);

		if(!last_cr)
			last_cr = gs->s;

		last_line_length = strlen(gs->s) - (last_cr - gs->s);

		if((last_line_length + extra_length) > gs->max_width)
			str_append(gs, "\\\n");
	}

	str_append(gs, str);

	if(sym && sym->type != S_UNKNOWN)
		str_printf(gs, " [=%s]", sym_str);
}

void expr_gstr_print(struct expr* e, struct gstr* gs)
{
	expr_print(e, expr_print_gstr_helper, gs, E_NONE);
}
